今日題目：104. Maximum Depth of Binary Tree

剛剛在群組看到在討論
想說也來寫一下哈哈哈哈

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:
Input: root = [1,null,2]
Output: 2

Example 3:
Input: root = []
Output: 0

Example 4:
Input: root = [0]
Output: 1

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• -100 <= Node.val <= 100

思路

使用BFS，以breadth為優先搜索

搜索過的root在進行判斷後，自list中刪除
如root尚有子點，則將其之子點append回list中

以此recursive後 即可獲得depth

My solution

def maxDepth(root):
    
    depth = 0
    q = [root]
    
    if root is None: return 0
    
    while len(q)!=0:
        depth +=1
        for i in range(q[0]):
            if q[0].left:
                q.append(q[0].left)
            if q[0].right:
                q.append(q[0].right)
            del q[0]
    return depth

Result

檢討

在討論區看到的解答

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

是使用DFS
以深度為優先搜索